/**
 * This file is part of Graph-Tool.
 * 
 * Graph-Tool is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 * 
 * Graph-Tool is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
 * A PARTICULAR PURPOSE. See the GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License along with
 * Graph-Tool. If not, see <http://www.gnu.org/licenses/>.
 */
package graphtool.graphs;

import java.util.Iterator;
import java.util.Vector;

import graphtool.math.matrices.IndexException;
import graphtool.math.matrices.MatrixPropertyException;
import graphtool.math.matrices.NMatrix;

/**
 * @author a.lunkeit - alunkeit(at)gmail(dot)com
 * 
 */
public class UndirectedGraph<V, E> extends BaseGraph<V, E>
{

  /**
   * Constructor
   */
  public UndirectedGraph()
  {
  }

  /**
   * The complement of a graph is G'(V, E') of a simple Graph G(V,E). It has the
   * same set of vertices but in G' two nodes are adjacent in case that they
   * aren't adjacent in G(V,E).
   * 
   * @return
   * @throws GraphPropertyException
   * @throws IndexException
   */
  @SuppressWarnings("unchecked")
  public UndirectedGraph<V, E> complement( EdgeProducer<V, E> eb ) throws GraphPropertyException
  {
    try
    {

      double[][] transformedA = new double[_adjacency.rows()][_adjacency.columns()];

      for( int i = 0; i < _adjacency.rows(); i++ )
      {
        for( int j = 0; j < _adjacency.columns(); j++ )
        {
          if( i == j )
            continue;

          double value = _adjacency.getValueAt( i, j );

          transformedA[i][j] = value > 0 ? 0 : 1;
        }
      }

      NMatrix transformedAM = new NMatrix( transformedA );
      NMatrix ut = transformedAM.getUpperTriangle();

      // 2. create nxm matrix as incidence matrix
      UndirectedGraph<V, E> ug = new UndirectedGraph<V, E>();
      ug._adjacency = transformedAM;
      ug._vertices = (Vector<V>) _vertices.clone();

      for( int i = 0; i < transformedAM.rows(); i++ )
      {
        if( 0 == ut.getRowSum( i ) )
          continue;

        V v1 = _vertices.get( i );

        double[] row = ut.getRow( i );

        for( int j = 0; j < row.length; j++ )
        {
          if( row[j] > 0 )
          {
            try
            {
              V v2 = _vertices.get( j );

              E e = eb.produce( v1, v2 );
              ug.addEdge( e, v1, v2 );
            }
            catch( Exception exc )
            {
              throw new GraphPropertyException( exc );
            }
          }
        }
      }

      return ug;
    }
    catch( MatrixPropertyException mpe )
    {
      throw new GraphPropertyException( mpe );
    }
    catch( IndexException ie )
    {
      throw new GraphPropertyException( ie );
    }
  }
  
  /**
   * Creates the joint set of both graphs (this and the given argument). The join-operation
   * does not take effect on <code>this</code>, the result of the operation is returned as
   * a new object.
   * 
   * @param ug
   * @param c
   * @return
   * @throws GraphPropertyException
   * @throws CloneNotSupportedException 
   */
  public UndirectedGraph<V,E> join( UndirectedGraph<V,E> ug ) throws GraphPropertyException
  {
    UndirectedGraph<V, E> result = (UndirectedGraph<V, E>) this.deepCopy();
    
    Iterator<V> vIter = ug.getVertices().iterator();
    
    while( vIter.hasNext())
    {
      V v = vIter.next();
      
      if( !containsEndpoint( v ))
      {
        result.addNode( v );
      }
    }
    
    Iterator<E> eIter = ug.getEdges().iterator();
    
    while( eIter.hasNext())
    {
      E e = eIter.next();
      
      if( !containsEdge( e ))
      {
        Pair<V,V> p = ug.getEndpoints( e );
        
        result.addEdge( e, p.getKey(), p.getValue());
      }
    }
    
    return result;
  }
  
  /**
   * Provides a subgraph containing all elements which are contained in both graphs.
   * 
   * @param ug
   * @return
   * @throws GraphPropertyException
   */
  public UndirectedGraph<V,E> intersection( UndirectedGraph<V,E> ug ) throws GraphPropertyException
  {
    UndirectedGraph<V, E> result = new UndirectedGraph<V,E>();
    
    Iterator<V> vIter = ug.getVertices().iterator();
    
    while( vIter.hasNext())
    {
      V v = vIter.next();
      
      if( containsEndpoint( v ))
      {
        result.addNode( v );
      }
    }
    
    Iterator<E> eIter = ug.getEdges().iterator();
    
    while( eIter.hasNext())
    {
      E e = eIter.next();
      
      if( containsEdge( e ))
      {
        Pair<V,V> p = ug.getEndpoints( e );
        
        result.addEdge( e, p.getKey(), p.getValue());
      }
    }
    
    return result;
  }
  
  /**
   * Removes the elements of the subgraph from <code>this</code> and returns the remaining
   * sub-graph. The function does not ensure that <code>ug</code> is exactly an subgraph of
   * <code>this</code>. Other functions have to be used to ensure this.
   * 
   * @param ug
   * @return
   * @throws GraphPropertyException
   */
  public UndirectedGraph<V,E> remove( UndirectedGraph<V,E> ug ) throws GraphPropertyException
  {
    UndirectedGraph<V,E> g1 = this.deepCopy();
    
    Iterator<E> eIter = ug.getEdges().iterator();
    
    while( eIter.hasNext() )
    {
      E e = eIter.next();
      
      if( g1.containsEdge( e ))
      {
        Pair<V,V> p = g1.getEndpoints( e );
        g1.removeEdge( e, p.getKey(), p.getValue() );
      }
    }
    
    Iterator<V> vIter = ug.getVertices().iterator();
    
    while( vIter.hasNext() )
    {
      V v = vIter.next();
      
      if( g1.containsEndpoint( v ))
        g1.removeNode( v );
    }
    
    return g1;
  }
  
  /**
   * Tests if the specified graph is an subgraph of <this>. R
   * @param ug
   * @return <code>true</code> in case of a subgraph, <code>false</code> otherwise.
   */
  public boolean isSubgraph( UndirectedGraph<V,E> ug ) 
  {
    Iterator<E> iter = ug.getEdges().iterator();
    
    while( iter.hasNext())
    {
      E e = iter.next();
      
      if( !containsEdge( e ))
      {
        return false;
      }
    }
    
    Iterator<V> vIter = ug.getVertices().iterator();
    
    while( vIter.hasNext())
    {
      V v = vIter.next();
      
      if( !this.containsEndpoint( v ))
      {
        return false;
      }
    }
    
    return true;
  }
  
  @SuppressWarnings("unchecked")
  private UndirectedGraph<V,E> deepCopy()
  {
    try
    {
      UndirectedGraph<V,E> ug = new UndirectedGraph<V,E>();
      ug._adjacency = _adjacency.clone();
      ug._admittance = _admittance.clone();
      ug._degree = _degree.clone();
      ug._edges = (Vector<E>)_edges.clone();
      ug._incidence = _incidence.clone();
      ug._spanningTreeCnt = _spanningTreeCnt;
      ug._vertices = (Vector<V>)_vertices.clone();
      
      return ug;
    }
    catch( Exception e )
    {
      _logger.error( e.getMessage(), e );
      return null;
    }
  }
  
  /**
   * Returns a string representation of the graph
   */
  public String toString()
  {
    StringBuffer buffer = new StringBuffer();
    
    buffer.append( "------------ Undirected Gaph --------------\n" );
    buffer.append( "Count of edges: " + _edges.size() + "\n" );
    buffer.append( "Count of vertices: " + _vertices.size() + "\n" );
    
    buffer.append(  "Adjacence:\n" + _adjacency );
    buffer.append( "Incidence:\n" + _incidence );
    
    Iterator<E> eIter = _edges.iterator();
    
    while( eIter.hasNext())
    {
      E e = eIter.next();
      
      Pair<V,V> p = this.getEndpoints( e );
      
      buffer.append( "V: " + p.getKey() + " E: " + e + " V: " + p.getValue() + "\n" );
    }
    return buffer.toString();
  }

}
